#include <bits/stdc++.h>
using namespace std;

/*
1432. 改变一个整数能得到的最大差值
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个整数 num 。你可以对它进行以下步骤共计 两次：

选择一个数字 x (0 <= x <= 9).
选择另一个数字 y (0 <= y <= 9) 。数字 y 可以等于 x 。
将 num 中所有出现 x 的数位都用 y 替换。
令两次对 num 的操作得到的结果分别为 a 和 b 。

请你返回 a 和 b 的 最大差值 。

注意，新的整数（a 或 b）必须不能 含有前导 0，并且 非 0。

 

示例 1：

输入：num = 555
输出：888
解释：第一次选择 x = 5 且 y = 9 ，并把得到的新数字保存在 a 中。
第二次选择 x = 5 且 y = 1 ，并把得到的新数字保存在 b 中。
现在，我们有 a = 999 和 b = 111 ，最大差值为 888
示例 2：

输入：num = 9
输出：8
解释：第一次选择 x = 9 且 y = 9 ，并把得到的新数字保存在 a 中。
第二次选择 x = 9 且 y = 1 ，并把得到的新数字保存在 b 中。
现在，我们有 a = 9 和 b = 1 ，最大差值为 8
示例 3：

输入：num = 123456
输出：820000
示例 4：

输入：num = 10000
输出：80000
示例 5：

输入：num = 9288
输出：8700
 

提示：

1 <= num <= 10^8
*/

// 法一
// O(n^4)
class Solution {
public:
    int maxDiff(int num) {
        // int --> str 
        string str = to_string(num);
        int maxVal = num;
        int minVal = num;

        // 第一次 最大化方向
        // 遍历所有可能性 x->y
        for (char x = '0'; x <= '9'; x++) {
            for (char y = '0'; y <= '9'; y++) {
                string a = str;     // copy 一下原始str
                // 替换
                for (char &ch : a) {
                    if (ch == x)    ch = y;
                }
                // 跳过非法前导0
                if (a[0] == '0') continue;
                int aVal = stoi(a);

                // 最小化方向
                for (char p = '0'; p <= '9'; ++p) {
                    for (char q = '0'; q <= '9'; ++q) {
                        string b = str; // 复制原始字符串
                        // 执行替换操作：将所有p替换为q
                        for (char &c : b) {
                            if (c == p) c = q;
                        }
                        // 跳过前导零的情况（非法数字）
                        if (b[0] == '0') continue;
                        int bVal = stoi(b); // 转换为整数
                        
                        // 更新最大差值：当发现更大的a-b时记录
                        if (aVal - bVal > maxVal - minVal) {
                            maxVal = aVal;
                            minVal = bVal;
                        }
                    }
                }
            }
        }
        return maxVal - minVal;
    }
};

// 法二
// 贪心优化
class Solution {
public:
    int maxDiff(int num) {
        string s = to_string(num);
        string a = s, b = s;
        
        // 最大化 a: 将第一个非9的字符替换为9

        for (char &c : a) {
            if (c != '9') {
                char x = c;
                for (char &d : a) {
                    if (d == x) d = '9';
                }
                break;
            }
        }

        // 最小化 b:
        // 情况1：如果首位不是'1'，将所有首位字符替换为'1'
        if (b[0] != '1') {
            char x = b[0];
            for (char &c : b) {
                if (c == x) c = '1';
            }
        } 
        // 情况2：如果首位是'1'，将后续第一个非'0'和非'1'的字符替换为'0'
        else {
            for (char &c : b) {
                if (c != '0' && c != '1') {
                    char x = c;
                    for (char &d : b) {
                        if (d == x) d = '0';
                    }
                    break;
                }
            }
        }
        
        // 返回最大可能值和最小可能值的差
        return stoi(a) - stoi(b);
    }
};


// 哈希进一步便于观看
class Solution {
public:
    int maxDiff(int num) {
        string ss, s;        // ss存储最大化后的字符串，s存储最小化后的字符串
        ss = to_string(num);
        s = ss;
        char t;              // 记录需要替换的目标字符
        
        // 最大化处理：将第一个非9的字符替换为9
        for(int i = 0; i < ss.size(); i++){
            if(ss[i] != '9'){
                t = ss[i];   // 找到第一个非9的字符
                break;
            }
        }
        for(int i = 0; i < ss.size(); i++){
            if(ss[i] == t){
                ss[i] = '9'; // 将所有目标字符替换为9
            }
        }
        int n1 = stoi(ss);   // 转换为整数得到最大值
        
        // 最小化处理：根据首位字符是否为1进行不同处理
        map<char, int> mp;   // 原代码中的map未使用，可忽略
        for(int i = 0; i < s.size(); i++){
            if(i == 0 && s[i] != '1') {
                t = s[i];    // 首位非1，记录该字符用于替换为1
                break;
            } else {
                if(s[i] != '1' && s[i] != '0'){
                    t = s[i]; // 首位为1，记录后续第一个非0/1的字符
                    break;
                }
            }
        }
        char temp;
        if(t == s[0]) temp = '1'; // 若替换首位，替换为1
        else temp = '0';          // 否则替换为0
        for(int i = 0; i < s.size(); i++){
            if(s[i] == t) s[i] = temp; // 执行替换操作
        } 
        int n2 = stoi(s);        // 转换为整数得到最小值
        
        return n1 - n2;          // 返回最大差值
    }
};